package com.example.demo.leetcode.top;

import java.util.*;

/**
 * 实现LRU
 */
class LRUCache {


    Map<Integer,Node> map = new HashMap<Integer,Node>();

    LinkedList<Node> list = new LinkedList<Node>();

    int capcity;


    public LRUCache(int capacity) {
        this.capcity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            int val = map.get(key).val;
            //刷新node中的值
            put(key,val);
            return val;
        }
        return -1;
    }

    public void put(int key, int value) {

        Node node = new Node(key,value);
        //如果map中存在，覆盖map中的，然后删除doublelist中那个，再将新的Node塞入
        if(map.containsKey(key)){
            Node old = map.get(key);
            map.put(key,node);
            list.remove(old);
            list.addFirst(node);
        }else{
            //如果map中不存在，先校验是否溢出，
            if(list.size() == capcity){
                Node node1 = list.removeLast();
                map.remove(node1.key);
            }
            list.addFirst(node);
            map.put(key,node);

        }
    }

    class Node{
        int key,val;
        Node prev,next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }




    //继承LinkedHashmap实现LRUCache
    static class LRUMap<K, V> extends LinkedHashMap<K, V> {
        private static final long serialVersionUID = 6918023506928428613L;
        // 最大容量
        public static int MAX_SIZE = 10;


        public LRUMap(int cacheSize, float loadFactor, boolean accessOrder) {
            // initialCapacity应该是 总大小/0.75+1,防止因为扩容造成重新hash
            super((int) (Math.ceil(cacheSize/0.75)+1), loadFactor, accessOrder);
        }

        /**
         * 如果Map的尺寸大于设定的最大容量，返回true，再新加入对象时删除最老的对象
         */
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > MAX_SIZE;
        }
    }

    public static void main(String[] args) {
        Map<Integer, Integer> map=new LRUMap<Integer, Integer>(10,0.75f,true);
        LRUMap.MAX_SIZE=4;
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 4);
        map.get(3);
        map.put(5, 5);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.err.println(entry.getKey());
        }
        //打印结果是 2 4 3 5 ，实现了LRU的功能
    }
}